package leetcode_core.leetcode_6;

import java.util.Arrays;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年02月20日 22:07
 */
public class IsMatch {
    private int n;
    private int m;
    private int[][] memo;
    public boolean isMatch(String s, String p) {
        n = s.length();m = p.length();
        memo = new int[n][m];
        for(int i = 0;i<n;i++){
            Arrays.fill(memo[i],-1);
        }
        return dp(s.toCharArray(),0,p.toCharArray(),0);
    }
    //字符串匹配的过程就是(i++,j++)的过程
    //1.定义状态和选择
    //1.1 状态:s串哪些部分是已经检查过的,匹配了的?p串哪些部分是已经检查过的,匹配了的,那么状态就是s[i]和p[j]
    //1.2 选择:选择的话要基于匹配的过程进行推断
    //2. 定义dp数组/dp函数
    //2.1 可以看到我们这里,由于匹配的次数n是不确定的,因此最好有一个回溯的做法,因此采用dp函数的方法
    //2.2 定义dp函数:boolean dp(String s,int i,String p,int j)
    //2.3 含义:代表着s[0...i]到p[0...j]是否能够匹配上,为什么要这样定义含义后面再说

    //1.2.1 当s[i] == p[j]的时候,这时候就认为匹配成功,i++,j++
    //1.2.2 当s[i] != p[j]这时候要分类讨论
    // (a):当p[j] == '.',证明是通配符,于是i++,j++
    // (b):当p[j+1] == '*',证明当前字符是一个通配符,而且这个通配符可以匹配n次或者0次
    // (b-1):当决定匹配n次的时候,那么这时候,j不动,i++
    // (b-2):当决定匹配0次的时候,那么这时候j+=2,i不动
    // (c):其他情况,当它不是通配符的时候,那么直接匹配失败了,false

    //3. 定义base-case
    //3.1 当j == p.length()的时候,这时候就只要检查i == s.length?如果主串匹配完了,那么就匹配成功
    //3.2 当i == s.length()的时候,这时候证明主串匹配完了,还要检查模式串能不能匹配空串
    //3.2.1 检查是不是剩余的部分能够匹配空串(p.length()-j+1)%2 == 0 && p [j+1] == '*'
    //4. 定义返回值
    //4.1 根据定义,只需要返回dp(s,0,p,0)即可
    //5. 优化重叠子问题
    //将所有的dp递推函数拿出来
    // dp(s,i,p,j+2)
    // dp(s,i+1,p,j)
    // dp(s,i+1,p,j+1)

    private boolean dp(char[] s,int i,char[] p,int j){
        //base-case
        if(j == m){
            return i == n;
        }
        if(i == n){
            //检查能够成对出现的
            if((n-j)%2 == 1){
                return false;
            }
            for(;j+1<m;j+=2){
                if(p[j+1]!='*'){
                    return false;
                }
            }
            return true;
        }
        if(memo[i][j]!=-1){
            return memo[i][j] != 0;
        }
        boolean res = false;
        //具体的推导过程
        if(s[i] == p[j] || p[j] == '.'){
            if(j+1 < m && p[j] == '*'){
                res =  dp(s,i,p,j+2) //匹配0次
                        || dp(s,i+1,p,j);//匹配n次
            }else{
                res =  dp(s,i+1,p,j+1);//双指针步进
            }
        }else{
            if(j+1 < m && p[j] == '*'){
                //只能够匹配0次
                res =  dp(s,i,p,j+2);
            }else{
                res = false;
            }
        }
        memo[i][j] = res ?1:0;
        return res;
    }



}
